#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;

int M[10][10];
int m,n;

int dist[10];
bool visited[10];
bool S[10];

void BFS(int u)
{
	cout<<"BFS"<<endl;
	queue<int>Q;
	Q.push(u);
	visited[u] = true;


	while(!Q.empty())
	{
		int temp = Q.front();
		Q.pop();
		for(int i = 0; i < n; i++)
			if(M[temp][i] != INF && !visited[i])
			{
				Q.push(i);
				cout<<i<<endl;
				visited[i] = true;
			}

	}
}

void Init()
{
	cout<<"m:";cin>>m;
	cout<<"n:";cin>>n;
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			if(i == j) M[i][j] = 0;
			else M[i][j] = INF;
		}


		dist[i] = INF;
		visited[i] = false;
		S[i] = false;
	}
	cout<<"u v w"<<endl;
	for(int i = 0; i < m; i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		M[u][v] = w;
	}
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			printf("%d%c",M[i][j], (j == n-1?'\n':'\t'));
	
}


bool check_S()
{
	bool flag = true;
	for(int i = 0; i < n; i++)
	{
		if(dist[i] == false)
			flag = false;
	}
	return flag;
}
void Dijkstra_(int u)
{
	//BFS
	S[u] = true;
	dist[u] = 0;
	for(int i = 0; i < n; i++)
	{
		dist[i] = M[u][i];
	}
	
	while(!check_S())
	{
		int Min = INF;
		int v = u;
		for(int i = 0; i < n; i++)
		{
			if(!S[i] && dist[i]< Min)
			{
				Min = dist[i];
				v = i;
			}
		}
		if(Min == INF) break;
		S[v] = true;
		cout<<"--------------------"<<endl;
		cout<<u<<Min<<endl;
		for(int i = 0; i < n; i++)
			printf("%d%c",S[i],(i == n-1?'\n':' '));
		cout<<"--------------------"<<endl;
		for(int i = 0; i < n; i++)
		{
			if(!S[i] && M[u][i] + dist[u] < dist[i])
			{
				dist[i] = dist[u] + M[u][i];  
			}
		}
	}
	
	return ;
}


void Dijkstra(int u)
{
	S[u] = true;
	dist[u] = 0;
	for(int i = 0; i < n; i++)
		dist[i] = M[u][i];

	for(int i = 1; i < n; i++)
	{
		int Min = INF;
		int v = u;
		for(int i = 0; i < n; i++)
		{
			if(!S[i] && dist[i] < Min)
			{
				Min = dist[i];
				v = i;
			}
		}

		S[v] = true;
		for(int i = 0; i < n; i++)
		printf("%d%c",dist[i],i == n-1 ? '\n':' ');

		for(int i = 0; i < n; i++)
		{
			if(!S[i] && dist[i] > dist[v] + M[v][i])
			{
				dist[i] = dist[v] + M[v][i];
			}
		}
	}
}

int main()
{
	Init();
	int u;
	cout<<"u: ";
	cin>>u;
	BFS(u);
	Dijkstra(0);
	for(int i = 0; i < n; i++)
		printf("%d%c",dist[i],(i == n-1 ? '\n':' '));


	return 0;
}
